from collections import Counter

def numTileOptions(tiles: str) -> int:
    count = 0
    freq = Counter(tiles)  # 统计每个字符的频率

    def dfs(used):
        nonlocal count
        for char in freq:
            if freq[char] > 0:
                freq[char] -= 1  # 使用一个字符
                used += 1
                count += 1  # 非空序列都算一个有效结果

                dfs(used)

                # 回溯
                freq[char] += 1
                used -= 1

    dfs(0)
    return count


# 测试用例
if __name__ == "__main__":
    test_cases = [
        ("abc", 15),
        ("Aab", 7),     # A, a, b, Aa, aA, Ab, bA
        ("AAAB", 19),   # 注意去重
        ("", 0),
        ("a", 1),
        ("ab", 4),
        ("aba", 8),
    ]

    for i, (tiles, expected) in enumerate(test_cases):
        result = numTileOptions(tiles)
        print(f"测试用例 {i+1}: tiles={tiles} => 结果: {result}, {'通过' if result == expected else '失败'}")